package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.concurrent.*;

/**
 * 基数排序 桶排序
 * 准备10个桶 索引为0-9 每个索引的桶放对应分位值（十分位、百分位 等）为索引的
 * 第一轮
 *  以个位数 为参考 放入对应的桶中 然后将桶从0-9 顺序将所有数据赋值到arr中
 * 第二轮
 *  以十位数 为参考 放入对应的桶中 然后将桶从0-9 顺序将所有数据赋值到arr中
 *
 * 一共执行 最大数的长度轮
 *
 *
 */
public class BaseSort {

    public static void main(String[] args) throws ExecutionException, InterruptedException {

        int size = 8000000;
        ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(5, 10, 15, TimeUnit.SECONDS, new ArrayBlockingQueue<>(5), Executors.defaultThreadFactory(),
                new ThreadPoolExecutor.CallerRunsPolicy());

        // 异步执行
        CompletableFuture<Void> runAsync = CompletableFuture.runAsync(() -> {

            int[] testArr = new int[size];
            for (int i = 0; i < testArr.length; i++) {
                testArr[i] = (int) (Math.random() * size);
            }
            Instant start = Instant.now();
            baseSort(testArr);       // 7218 毫秒
            Instant end = Instant.now();
            System.out.println("慢：" + Duration.between(start, end).toMillis());
            //        System.out.println(Arrays.toString(testArr));

        }, threadPoolExecutor);

        CompletableFuture<Void> runAsync1 = CompletableFuture.runAsync(() -> {
            int[] testArr = new int[size];
            for (int i = 0; i < testArr.length; i++) {
                testArr[i] = (int) (Math.random() * size);
            }
            Instant start = Instant.now();
            baseSort1(testArr);       // 17 毫秒
            Instant end = Instant.now();
            System.out.println("快：" + Duration.between(start, end).toMillis());
//            System.out.println(Arrays.toString(testArr));
        }, threadPoolExecutor);

        // 等待上面异步执行执行完成 可以等待多个 必须得等上面的两个异步任务执行完成才能执行下面的事情
        CompletableFuture.allOf(runAsync1, runAsync).get();  // 不等待的话 上面两个和main就会随机执行
        System.out.println("执行完成");
        threadPoolExecutor.shutdown();

//        int size = 8;
//        int[] testArr = new int[size];
//        for (int i = 0; i < testArr.length; i++) {
//            testArr[i] = (int) (Math.random() * 80000);
//        }
//        System.out.println(Arrays.toString(testArr));
//
//        Instant start = Instant.now();
//        baseSort1(testArr);
//        Instant end = Instant.now();
//        System.out.println(Duration.between(start, end).toMillis()); //15
//        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 基数排序
     *
     * @param arr
     */
    public static void baseSort(int[] arr) {
        int[][] tempArr = new int[10][arr.length];
        int[] indexArr = new int[10]; // 记录每个桶的索引位置
        int temp = 0;
        int maxLength = maxLength(arr);


        // 执行 最大数据长度那么多轮
        for (int i = 0; i < maxLength; i++) {
            // 将数据放入桶中
            for (int j = 0; j < arr.length; j++) {
                temp = arr[j];    // 要存放的数据
                // 封装数据 对于 不足maxLength长度的前面用0补齐
                String tempStr = temp + "";
                int tempLength = tempStr.length();
                if (tempLength <= maxLength) {
                    int num = maxLength - tempLength;
                    while (num > 0) {
                        tempStr = "0" + tempStr;
                        num--;
                    }
                }
                // 获取该数应该存放到那个桶中 // 要存放数据应该存放到那个桶的索引
                // maxLength - i - 1 获取位数的值
                int index = Integer.parseInt(tempStr.toCharArray()[maxLength - i - 1] + "");   // 从 个位  十位  百位 。。。
                tempArr[index][indexArr[index]] = temp;
                indexArr[index] = indexArr[index] + 1;
            }
            int arrIndex = 0;
            // 将桶中的数据 赋值给arr
            for (int j = 0; j < 10; j++) {
                // 遍历这个桶中的所有数据
                for (int k = 0; k < indexArr[j]; k++) {
                    arr[arrIndex++] = tempArr[j][k];
                }
                indexArr[j] = 0;  //将桶的索引位置清0
            }
        }
    }

    /**
     * 这个比上面那个更快  因为 在讲不足最大长度的数据前面补0的时候 这里只是补了一次 上面补了很多次 用到那个数据一次就补一次
     * @param arr
     */
    public static void baseSort1(int[] arr) {
        String[][] tempArr = new String[10][arr.length];
        int[] indexArr = new int[10]; // 记录每个桶的索引位置
        int maxLength = maxLength(arr);

        // 将不足maxLength 的数据前面补0
        String[] arrStr=new String[arr.length];
        for(int i=0;i<arr.length;i++){
            String tempStr = arr[i] + "";
            int tempLength = tempStr.length();
            if (tempLength <= maxLength) {
                int num = maxLength - tempLength;
                while (num > 0) {
                    tempStr = "0" + tempStr;
                    num--;
                }
            }
            arrStr[i]=tempStr;
        }

        // 执行 最大数据长度那么多轮
        for (int i = 0; i < maxLength; i++) {
            // 将数据放入桶中
            for (int j = 0; j < arrStr.length; j++) {

                // 获取该数据要放到那个桶中（获取桶的索引 就是二维数组的行的索引）
                int index = Integer.parseInt(arrStr[j].toCharArray()[maxLength - i - 1] + "");   // 从 个位  十位  百位 。。。
                tempArr[index][indexArr[index]] = arrStr[j];    // 将数据放入桶中
                indexArr[index] = indexArr[index] + 1;  // 记录桶的索引
            }
            int arrIndex = 0;
            // 将桶中的数据 赋值给arr
            for (int j = 0; j < 10; j++) {
                // 遍历这个桶中的所有数据
                for (int k = 0; k < indexArr[j]; k++) {
                    arrStr[arrIndex++] = tempArr[j][k];
                }
                indexArr[j] = 0;  //将桶的索引位置清0
            }
        }
        // 将补0 的数据 放入arr中保存
        for(int i =0;i<arr.length;i++){
            arr[i]=Integer.parseInt(arrStr[i]);
        }
    }

    /**
     * 获取数组中最大数的数长度
     *
     * @param arr
     * @return
     */
    public static int maxLength(int arr[]) {

        int maxLength = 0;
        String temp = "";
        for (int i = 0; i < arr.length; i++) {
            temp = arr[i] + "";
            maxLength = maxLength > temp.length() ? maxLength : temp.length();
        }
        return maxLength;
    }
}
